class Solution {
public:
    string reverseWords(string s) {

        //双指针
        // std::reverse(s.begin(),s.end());
        // int index = 0;
        // for(int i = 0;i<s.length();++i)
        // {
        //     if(s[i] != ' ')
        //     {
        //         if(index != 0)
        //         s[index++] = ' ';
        //         int begin = index;
        //         while(i < s.length() && s[i] != ' ')
        //         {
        //             s[index++] = s[i++];
        //         }
        //         int end = index;
        //         std::reverse(s.begin()+begin,s.begin()+end);
        //         //注意：stl容器中凡是进行范围操作的一般都是左闭右开[first,last)
        //     }
        // }
        // return s.substr(0,index);
        //双指针
        //首先反转给定字符串s
        // std::reverse(s.begin(),s.end());
        // int size = s.size();
        // int index = 0;
        // for(int i = 0;i < size;++i)
        // {
        //     if(s[i] != ' ')
        //     {
        //         if(index != 0)
        //         s[index++] = ' ';
        //         int start = i;
        //         while(start < size && s[start] != ' ')
        //         {
        //             s[index++] = s[start++];
        //         }
        //         std::reverse(s.begin()+index-(start-i), s.begin()+index);
        //         i = start;
        //     }
        // }
        // s.erase(index); //s.erase(s.begin()+index,s.end());删除后面的空格
        // return s;
        //index相当于一个慢指针
        //start相当于一个临时快指针
        
        //栈：
        int size = s.size();
        string res;
        stack<string> mystack;
        for(int i = 0;i<size;++i)
        {
            if(' ' == s[i])
            {
                if(!res.empty())
                {
                    mystack.push(res);
                    res.clear();
                }
            }
            else
            res.push_back(s[i]);
        }
        while(!mystack.empty())
        {
            if(!res.empty())
            res += ' ';
            res += mystack.top();
            mystack.pop();
        }
        //处理res中最后一个' '  //这种写法很挫，因此上面对该代码做了优化，如果res不为空就给添加' '
        // size = res.size();
        // res.erase(size-1);
        return res;
    }
};


//最长公共前缀
string longestPrefix(const vector<string>& vv)
{
	size_t size = vv.size();
	if (size == 0) {
		return "";
	}
	else if (size == 1) {
		return vv[0];
	}
	string str = vv[0];
	for (int i = 0;i < str.length();++i)
	{
		for (int j = 1;j < vv.size();++j)
		{
			if (i > vv[j].size() - 1 || str[i] != vv[j][i]) {
				return str.substr(0, i);
			}
		}
	}
	return str;
}